150B - Quantity of Strings - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
int n,m,k,p,a[2005],num;
long long ans=1,mod=1e9+7;
int A(int x){
	if(x==a[x])return x;
	a[x]=A(a[x]);
	return a[x];
}
int main(){
	cin>>n>>m>>k;
	num=n;
	for(int i=1;i<=n;i++)a[i]=i;
	for(int i=1;i<=n-k+1;i++){
		for(int I=i,J=i+k-1;I<J;I++,J--){
			if(A(I)!=A(J))num--;
			a[a[I]]=A(J);
		}
	}
	for(int i=1;i<=num;i++)ans*=m,ans%=mod;
	cout<<ans;
  	return 0;
}